package a1sort.a2heapsort;

import java.util.Arrays;
import java.util.Random;

/**
 * @author zhangMr
 * @description
 * 堆排序-参考算法导论第六章
 * 运行时间n㏒n
 * **/
public class HeapSort {
    //获取父节点索引
    public static int getParentIndex(int i){
        if(i%2==0){
            return (i-2)/2;
        }else{
            return (i-1)/2;
        }

    }
    //获取子左节点索引
    public static int getLeftIndex(int i){
        return 2*i+1;
    }
    //获取子右节点索引
    public static int getRightIndex(int i){
        return 2*i+2;
    }
    //维护heap性质
    public static void maxHeapify(Integer[] data,int index){
        int largest=index;
        int leftIndex=getLeftIndex(index);
        int rightIndex=getRightIndex(index);
        int currentData=data[index];
        if(leftIndex<data.length&&data[leftIndex]>currentData){
            largest=leftIndex;
            currentData=data[leftIndex];
        }
        if(rightIndex<data.length&&data[rightIndex]>currentData){
            largest=rightIndex;
            currentData=data[rightIndex];
        }
        if(largest!=index){
            data[largest]=data[index];
            data[index]=currentData;
            //递归调用
            maxHeapify(data,largest);
        }
    }
    //创建最大堆
    public static void bulidMapHeap(Integer[] data){
        int middle=data.length/2-1;
        for(int i=middle;i>=0;i--){
            maxHeapify(data,i);
        }
    }
    //使用堆进行排序
    public static Integer[] heapSort(Integer[] data){
        Integer[] result=new Integer[data.length];
        bulidMapHeap(data);
        for(int i=0;i<data.length;i++){
            result[i]=data[0];
            data[0]=Integer.MIN_VALUE;
            maxHeapify(data,0);
        }
        return result;
    }

    public static void main(String[] args) {
        Random random=new Random();
        Integer[]data=new Integer[10];
        for(int i=0;i<10;i++){
            data[i]= random.nextInt(100);
        }
        System.out.println("随机生成的数组"+ Arrays.toString(data));
        Integer[] result= heapSort(data);
        System.out.println("排序后的数组"+Arrays.toString(result));
    }
}
